using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0785. 判断二分图")]
    public class No0785_IsBipartite : AbsBaseTestItem
    {
        /*
        给定一个无向图graph，当这个图为二分图时返回true。

        如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

        graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

        注意:
            graph 的长度范围为 [1, 100]。
            graph[i] 中的元素的范围为 [0, graph.length - 1]。
            graph[i] 不会包含 i 或者有重复的值。
            图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。
        */

        public override void OnTest()
        {
            Assert.TestExe(IsBipartite,
                new int[][] {
                    new int[] {1, 3},
                    new int[] {0, 2},
                    new int[] {1, 3},
                    new int[] {0, 2},
                }, true);

            Assert.TestExe(IsBipartite,
                new int[][] {
                    new int[] {1,2,3},
                    new int[] {0,2},
                    new int[] {0,1,3},
                    new int[] {0,2},
                }, false);
        }

        /// <summary>
        ///  方法二：广度优先搜索
        /// </summary>
        public bool IsBipartite(int[][] graph)
        {
            const int UNCOLORED = 0;
            const int RED = 1;
            const int GREEN = 2;
            int n = graph.Length;
            int[] color = new int[n];
            Array.Fill(color, UNCOLORED);
            for (int i = 0; i < n; ++i)
            {
                if (color[i] != UNCOLORED)
                {
                    continue;
                }
                Queue<int> queue = new Queue<int>();
                queue.Enqueue(i);
                color[i] = RED;
                while (queue.Count > 0)
                {
                    int node = queue.Dequeue();
                    int cNei = color[node] == RED ? GREEN : RED;
                    foreach (int neighbor in graph[node])
                    {
                        if (color[neighbor] == UNCOLORED)
                        {
                            queue.Enqueue(neighbor);
                            color[neighbor] = cNei;
                        }
                        else if (color[neighbor] != cNei)
                        {
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    }
}
